package 图;

import java.util.List;
import java.util.Map;
import java.util.Set;

import 图.Graph.EdgeInfo;
import 图.Graph.PathInfo;
import 图.Graph.Visitor;
import 图.Graph.WeightManager;

public class Main {

	private static WeightManager<Double> weightManager = new WeightManager<Double>() {

		@Override
		public int compare(Double e1, Double e2) {
			return e1.compareTo(e2);
		}

		@Override
		public Double add(Double e1, Double e2) {
			return e1 + e2;
		}

		@Override
		public Double zero() {
			return 0.0d;
		}

	};

	public static void main(String[] args) {
		// testMst();
		// testBfs();
		// testDfs();
		// testTopologicalSort();
//		 testDijkstra();
//		testBellmanFord();
		testFloyd();
//		System.out.println(5 % 1);
	}

	private static void testFloyd() {
		Graph<Object, Double> graph = directedGraph(Data.NEGATIVE_WEIGHT1);
		Map<Object, Map<Object, PathInfo<Object, Double>>> paths = graph.shortestPath();
		paths.forEach((Object v, Map<Object, PathInfo<Object, Double>> map) -> {
			System.out.println("-------------"+v+"-----------");
			map.forEach((Object obj, PathInfo<Object, Double> info) -> {
				System.out.println(obj + "____" +info);
			});
		});
	}

	private static void testBellmanFord() {
		Graph<Object, Double> graph = directedGraph(Data.NEGATIVE_WEIGHT1);
		Map<Object, PathInfo<Object, Double>> map = graph.shortestPath("A");
		if (map == null)
			return;
		map.forEach((Object value, PathInfo<Object, Double> info) -> {
			System.out.println(value + "_" + info);
		});
	}

	private static void testDijkstra() {
		Graph<Object, Double> graph = directedGraph(Data.NEGATIVE_WEIGHT1);
		Map<Object, PathInfo<Object, Double>> map = graph.shortestPath("A");
		map.forEach((Object value, PathInfo<Object, Double> info) -> {
			System.out.println(value + "_" + info);
		});
	}

	private static void testDfs() {
		Graph<Object, Double> graph = directedGraph(Data.DFS_02);
		graph.dfs("a", new Visitor<Object>() {
			@Override
			public boolean visit(Object value) {
				System.out.println(value);
				return false;
			}
		});
	}

	private static void testBfs() {
		Graph<Object, Double> graph = undirectedGraph(Data.BFS_01);
		graph.bfs("A", new Visitor<Object>() {
			@Override
			public boolean visit(Object value) {
				System.out.println(value);
				return false;
			}
		});
	}

	private static void testMst() {
		Graph<Object, Double> graph = undirectedGraph(Data.MST_01);
		Set<EdgeInfo<Object, Double>> mst = graph.mst();
		for (EdgeInfo<Object, Double> edgeInfo : mst) {
			System.out.println(edgeInfo);
		}
	}

	private static void testTopologicalSort() {
		Graph<Object, Double> graph = directedGraph(Data.TOPO);
		List<Object> list = graph.topologicalSort();
		System.out.println(list);
	}

	/**
	 * 有向图
	 */
	private static Graph<Object, Double> directedGraph(Object[][] data) {
		Graph<Object, Double> graph = new ListGraph<>(weightManager);
		for (Object[] edge : data) {
			if (edge.length == 1) {
				graph.addVertex(edge[0]);
			} else if (edge.length == 2) {
				graph.addEdge(edge[0], edge[1]);
			} else if (edge.length == 3) {
				double weight = Double.parseDouble(edge[2].toString());
				graph.addEdge(edge[0], edge[1], weight);
			}
		}
		return graph;
	}

	/**
	 * 无向图
	 * 
	 * @param data
	 * @return
	 */
	private static Graph<Object, Double> undirectedGraph(Object[][] data) {
		Graph<Object, Double> graph = new ListGraph<>(weightManager);
		for (Object[] edge : data) {
			if (edge.length == 1) {
				graph.addVertex(edge[0]);
			} else if (edge.length == 2) {
				graph.addEdge(edge[0], edge[1]);
				graph.addEdge(edge[1], edge[0]);
			} else if (edge.length == 3) {
				double weight = Double.parseDouble(edge[2].toString());
				graph.addEdge(edge[0], edge[1], weight);
				graph.addEdge(edge[1], edge[0], weight);
			}
		}
		return graph;
	}
}
